Finding the successor or
predecessor of a key in a BST uses two symmetric cases.
- Successor, Case 1: If k has a right child, go right once and then as far left as possible to find the smallest key there.
- Successor, Case 2: If there is no right subtree, traverse from the root, keeping track of the last node where you turned left. That node is the successor.
- Predecessor: Symmetric logic. Case 1: go left once, then as far right as possible. Case 2: from the root, track the last right turn.
def successor(root, key):
# First, find the node for the given key (guaranteed to exist)
node_k = root
while node_k and node_k.key != key:
if key < node_k.key:
node_k = node_k.left
else:
node_k = node_k.right
# Case 1: Node has a right subtree.
if node_k and node_k.right is not None:
current = node_k.right
while current.left is not __________:
current = __________
return current.key
# Case 2: No right subtree.
successor_candidate = None
current = root
while current and current.key != key:
if key < current.key:
# Potential successor found, go left for a better one.
successor_candidate = current.key
current = current.left
else:
# Not a potential successor, just go right.
current = __________
return successor_candidate
def predecessor(root, key):
# TODO: Implement predecessor with symmetric logic.
pass
Copied!